package com.example.summary.leetcode;

import com.alibaba.fastjson.JSON;

import java.util.ArrayList;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;

/**
 * Created by wzn on 2019/9/10.
 */
public class LeetCode107 {

    public static void main(String[] args) {
        TreeNode p = new TreeNode(1);

        TreeNode three = new TreeNode(3);
        TreeNode four = new TreeNode(4);

        p.left = three;
        p.right = four;

        System.out.println(JSON.toJSONString(levelOrderBottom(p)));
    }

    public static List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> listList = new ArrayList<>();
        levelOrderBottomItem(root, listList, 0);
        return listList;
    }

    static void levelOrderBottomItem(TreeNode root, List<List<Integer>> values, int cenci) {
        if (null == root) {
            return;
        }

        List<Integer> cenCiList;
        if (values.size() <= cenci) {
            cenCiList = new ArrayList<>();
            values.add(0, cenCiList);
        }
        cenCiList = values.get(values.size() - 1 - cenci);

        levelOrderBottomItem(root.left, values, cenci + 1);
        levelOrderBottomItem(root.right, values, cenci + 1);

        cenCiList.add(root.val);

    }

    public static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }
}
